/*
 * hash_table.h - Hashtable
 * Clunix, cezanne@clunix.com, 2004.10
 *
 * $Id: hash_table.h,v 1.1.1.1 2007/10/01 01:05:18 cezanne Exp $
 *
 * Copyright (c) 2004-2005 by Clunix Inc. All Rights Reserved.
 */

#ifndef _ECM_HASH_TABLE_H_
#define _ECM_HASH_TABLE_H_

#ifdef __cplusplus
extern "C" {
#endif

#define ECM_HEURISTICS_NONE          0
#define ECM_HEURISTICS_TRANSPOSE     1
#define ECM_HEURISTICS_MOVE_TO_FRONT 2
#define ECM_AUTOMATIC_REHASH         4

/**
 * The structure for hash keys. You should not care about this
 * structure unless you plan to write your own hash functions.
 */
typedef struct s_hash_key
{
	unsigned int	i_size;
	ecm_ptr_t	p_key;
} ecm_hashkey_t;

/*
 * The structure for hash entries.
 */
typedef struct s_hash_entry
{
	void *p_data;

	struct s_hash_entry *p_next;
	struct s_hash_entry *p_prev;
	ecm_hashkey_t key;
} ecm_hashentry_t;

typedef struct {
	ecm_uint32	i_curr_bucket;
	ecm_hashentry_t	*p_entry;
	ecm_hashentry_t *p_next;
} ht_iterator_t;

/**
 * Definition of the hash function pointers. @c ecm_fn_hash_t should be
 * used when implementing new hash functions. Look at the supplied
 * hash functions, like @c ecm_one_at_a_time_hash(), for examples of hash
 * functions.
 *
 * @param p_key the key to calculate the hash value for.
 *
 * @return a 32 bit hash value.
 *
 * @see @c ecm_one_at_a_time_hash(), @c ecm_rotating_hash(),
 *      @c ecm_crc_hash()
 */
typedef ecm_uint32 (*ecm_fn_hash_t)(ecm_hashkey_t *p_key);

/*
 * The hash table structure.
 */
typedef struct
{
	unsigned int	i_items;	/**< The current number of items in the table */
	unsigned int	i_size;		/** number of buckets */
	ecm_fn_hash_t	fn_hash;	/**< The hash function used */
	int		i_heuristics;	/**< The type of heuristics used */
	int		i_automatic_rehash;
				/**< TRUE if automatic rehashing is used */

	/* private: */
	ecm_hashentry_t	**pp_entries;
	int		*p_nr;	/* The number of entries in each bucket */
	int		i_size_mask;	/* The number of bits used in the size */
	ecm_mutex_t	lock;
} hashtable_t;

void ecm_hashtable_sethash(ecm_hashtable_t ht, ecm_fn_hash_t fn_hash);
void ecm_hashtable_set_heuristics(ecm_hashtable_t ht, int i_heuristics);
void ecm_hashtable_set_autorehash(ecm_hashtable_t ht, ECMBOOL b_rehash);
ecm_uint32 ecm_hashtable_get_tablesize(ecm_hashtable_t ht);
void ecm_hashtable_rehash(ecm_hashtable_t ht, unsigned int i_size);

ecm_uint32 ecm_one_at_a_time_hash(ecm_hashkey_t *p_key);
ecm_uint32 ecm_rotating_hash(ecm_hashkey_t *p_key);
ecm_uint32 ecm_crc_hash(ecm_hashkey_t *p_key);

#ifdef __cplusplus
}
#endif

#endif /* _ECM_HASH_TABLE_H_ */
